package algorithms.leaning.class23;

import common.util.MyUtil;

/**
 * 给定一个正数数组arr，请把arr中所有的数分成两个集合
 * 如果arr长度为偶数，两个集合包含数的个数要一样多
 * 如果arr长度为奇数，两个集合包含数的个数必须只差一个
 * 请尽量让两个集合的累加和接近
 * 返回：
 * 最接近的情况下，较小集合的累加和
 *
 * @author guichang
 * @date 2021/6/25
 */

@SuppressWarnings("all")
public class Code2_动态规划_累加和最接近_奇偶 {
    public static void main(String[] args) {
        int[] nums = MyUtil.createArray(1, 10, 5, 20, 1);
        MyUtil.print(minSum(nums)); // 15
    }

    public static int minSum(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int N = nums.length;
        int sum = 0;
        for (int x : nums) {
            sum += x;
        }
        sum /= 2;
        // 偶数
        if ((N & 1) == 0) {
            return process(nums, 0, N / 2, sum);
        }
        // 奇数
        int p1 = process(nums, 0, N / 2, sum);
        int p2 = process(nums, 0, N / 2 + 1, sum);
        return Math.max(p1, p2);
    }

    /**
     * 当前来到了index，还能拿count个数，累加和<=rest的最大值
     * TODO 有点问题
     */
    private static int process(int[] nums, int index, int count, int rest) {
        if (index == nums.length) {
            return 0;
        }
        if (count == 0) {
            return 0;
        }
        // 不要index的数
        int p1 = process(nums, index + 1, count, rest);
        // 有可能要index的数
        int p2 = 0;
        if (rest - nums[index] >= 0) {
            p2 = nums[index] + process(nums, index + 1, count - 1, rest - nums[index]);
        }
        return Math.max(p1, p2);
    }
}